// 99. 恢复二叉搜索树
// https://leetcode.cn/problems/recover-binary-search-tree/

/**
示例 1：
输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：
输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。
 */

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function (root) {
    const flatArr = centerScan(root);
    const sortArr = flatArr.map((node) => node.val).sort((a, b) => a - b);

    for (let i = 0; i < sortArr.length; i++) {
        if (sortArr[i] !== flatArr[i].val) {
            console.log(`got ${sortArr[i]} != ${flatArr[i].val}`);
            flatArr[i].root.val = sortArr[i];
        }
    }
};

function centerScan(root) {
    if (!root || root.val === null) return [];
    if (root.left === null && root.right === null)
        return { val: root.val, root };

    let leftArr = centerScan(root.left);
    let rightArr = centerScan(root.right);

    return [].concat(leftArr).concat({ val: root.val, root }).concat(rightArr);
}

function TreeNode(val, left, right) {
    this.val = val === undefined ? 0 : val;
    this.left = left === undefined ? null : left;
    this.right = right === undefined ? null : right;
}

function genTreeNode(arr) {
    console.log(`${JSON.stringify(arr)}`);
    let arrNode = arr.map((i) => (i != null ? new TreeNode(i) : null));
    for (let i = 0; i < arrNode.length; i++) {
        const leftIndex = 2 * i + 1;
        const rightIndex = 2 * i + 2;

        if (leftIndex >= arrNode.length) break;

        if (arrNode[i] !== null && arrNode[i].val !== null) {
            arrNode[i].left = arrNode[leftIndex];
            arrNode[i].right = arrNode[rightIndex];
        }
    }

    return arrNode[0];
}

recoverTree(genTreeNode([1, 3, null, null, 2]));
